1. Field of the Invention
The present invention relates to an error correction decoding field, and more particularly, to a Reed-Solomon (RS) decoder and a decoding method.
2. Description of the Related Art
An RS decoder is mainly used for correcting errors generated during transmission in a digital communications system using a high definition television (HDTV), a digital versatile disc (DVD), or a compact disc (CD), and has excellent error correcting performance. However, the RS decoder has a very complicated structure. In general, an RS code is expressed as RS(N,I). One packet is comprised of N symbols. Among these symbols, I symbols show a message. The remaining N-I symbols show a parity. Each symbol is comprised of m bits.
FIG. 1 is a block diagram of a conventional RS decoder using a modified Euclidean algorithm, which is described in the document [1]: "On the VLSI Design of a Pipeline Reed-Solomon Decoder Using Systolic Arrays", H. M. Shao and I. S. Reed, IEEE Trans. Comput, vol. 37, October. 1988, pp. 1273-1280.
The conventional polynomial expansion of two parts, a first polynomial expander 106 expands an initial error locator polynomial using the root .alpha..sup.-k of the initial error locator polynomial on erasure information previously stored in an .alpha..sup.-k generator 102. A second polynomial expander 108 expands a modified syndrome polynomial using the syndrome polynomial calculated by a first polynomial calculator 104. The coefficients of the syndrome polynomial becomes each calculated syndrome value. Also, an erasure means an error in which the location is known from received data. An error means an error, the location and magnitude of which are known.
In the parallel expansion method provided in the document [1], when the number of errors capable of being corrected is t, since the first polynomial expander 106 must calculate 2t+1 coefficients because the initial error locator polynomial has 2t degrees, 2t+1 registers of m-bit(8-bit) must exist as shown in FIG. 2. Also, 2t+1 multipliers and 2t+1 adders are necessary for expanding the initial error locator polynomial.
Since the second polynomial expander 108 for generating the modified syndrome polynomial must calculate 2t coefficients because the modified syndrome polynomial has 2t-1 degrees, 2t registers, 2t multipliers, and 2t adders for calculating and storing the 2t coefficients are necessary as shown in FIG. 3. A previously calculated syndrome is provided to each register as an initial value. The operation of the iterative equation shown in Equation 7 is performed with respect to the syndrome input according to a clock signal (CLK). Accordingly, the respective coefficients of the modified syndrome polynomial are obtained after a clock time of 2t.
Therefore, in the RS decoder employing a conventional parallel expansion method, the number of multipliers required for calculating the polynomial is the sum of the multipliers used during calculating the modified syndrome polynomial and the initial error locator polynomial, i.e., 2t+2t+1(=4t+1).
Since the operation used in the RS decoder is performed on the Galois Field, the multiplier is not a general decimal multiplier but a Galois field multiplier. Accordingly, the structure of the Galois field multiplier becomes more complicated. Since the Galois Field multiplier requires largest number of gates in realizing an integrated circuit of the RS decoder, the complexity remarkably increases as the number (t) of errors capable of being corrected increases in order to calculate the polynomial by the parallel expansion method.